package com.cy.algorithm.binarytree.cover;

import cn.hutool.core.collection.ListUtil;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;

/**
 * 非递归遍历二叉树
 *
 * @author chen_yu
 * @date 2020年12月13日20:17:57
 */
public class UnRecursiveBinaryTree {


    public static void main(String[] args) {
        TreeNode<String> node =
                new TreeNode<>("A",
                        new TreeNode<>("B", new TreeNode<>("D", new TreeNode<>("G"), new TreeNode<>("H"))),
                        new TreeNode<>("C", new TreeNode<>("E", null, new TreeNode<>("I")), new TreeNode<>("F"))
                );

        List<String> stringList = preOrder(node);
        for (String s : stringList) {
            System.out.print(s + "->");
        }
        System.out.println();
        List<String> midOrder = midOrder(node);
        for (String s : midOrder) {
            System.out.print(s + "->");
        }
        System.out.println();
        List<String> afterOrder = afterOrder(node);
        for (String s : afterOrder) {
            System.out.print(s + "->");
        }
        System.out.println();
        List<String> strings = levelOrder(node);
        for (String s : strings) {
            System.out.print(s + "->");
        }
    }

    /**
     * 前序遍历
     *
     * @param node 根节点
     * @param <T>  泛型T
     */
    public static <T> List<T> preOrder(TreeNode<T> node) {
        List<T> list = ListUtil.list(false);
        if (node == null) {
            return list;
        }
        Stack<TreeNode<T>> stack = new Stack<>();
        stack.push(node);
        while (!stack.isEmpty()) {
            TreeNode<T> treeNode = stack.pop();
            list.add(treeNode.getData());
            if (treeNode.getRight() != null) {
                stack.push(treeNode.getRight());
            }
            if (treeNode.getLeft() != null) {
                stack.push(treeNode.getLeft());
            }
        }
        return list;
    }

    /**
     * 中序遍历
     *
     * @param node 根节点
     * @param <T>  泛型T
     */
    public static <T> List<T> midOrder(TreeNode<T> node) {
        List<T> list = ListUtil.list(false);
        if (node == null) {
            return list;
        }
        Stack<TreeNode<T>> stack = new Stack<>();
        TreeNode<T> p = node;
        while (p != null || !stack.isEmpty()) {
            if (p != null) {
                stack.push(p);
                p = p.getLeft();
                continue;
            }
            TreeNode<T> pop = stack.pop();
            list.add(pop.getData());
            p = pop.getRight();
        }
        return list;
    }

    /**
     * 后序遍历
     *
     * @param node 根节点
     * @param <T>  泛型T
     */
    public static <T> List<T> afterOrder(TreeNode<T> node) {
        List<T> list = ListUtil.list(false);
        if (node == null) {
            return list;
        }
        Stack<TreeNode<T>> stack = new Stack<>();
        TreeNode<T> p = node;
        // 标记最近出栈的节点，用于判断是否是p节点的右孩子，如果是的话，就可以访问p节点
        TreeNode<T> pre = p;
        while (p != null || !stack.isEmpty()) {
            if (p != null) {
                stack.push(p);
                p = p.getLeft();
                continue;
            }
            p = stack.pop();
            if (p.getRight() == null || p.getRight() == pre) {
                list.add(p.getData());
                pre = p;
                p = null;
                continue;
            }
            stack.push(p);
            p = p.getRight();
            stack.push(p);
            p = p.getLeft();
        }
        return list;
    }

    /**
     * 非递归层次遍历
     *
     * @param root
     * @param <T>
     * @return
     */
    public static <T> List<T> levelOrder(TreeNode<T> root) {
        List<T> res = ListUtil.list(false);
        if (root == null) {
            return res;
        }
        Queue<TreeNode<T>> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            // current node
            TreeNode<T> current = queue.remove();
            res.add(current.getData());

            if (current.getLeft() != null) {
                queue.add(current.getLeft());
            }
            if (current.getRight() != null) {
                queue.add(current.getRight());
            }
        }
        return res;
    }
}
